package main

func main() {
	l12 := ListNode{
		Val:  4,
		Next: nil,
	}
	l11 := ListNode{
		Val:  2,
		Next: &l12,
	}
	l1 := ListNode{
		Val:  1,
		Next: &l11,
	}

	l22 := ListNode{
		Val:  4,
		Next: nil,
	}
	l21 := ListNode{
		Val:  3,
		Next: &l22,
	}
	l2 := ListNode{
		Val:  1,
		Next: &l21,
	}

	mergeTwoLists(&l1, &l2)
}

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//
//
// 示例：
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
//
// Related Topics 链表


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val int
	Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// 加个链表头
	var l1Prefix, l2Prefix ListNode
	if l2 == nil {
		return l1
	} else if l1 == nil {
		return l2
	}
	l1Prefix.Next = l1
	l2Prefix.Next = l2
	l1 = &l1Prefix
	l2 = &l2Prefix
	for l1.Next != nil && l2.Next != nil {
		if l1.Next.Val <= l2.Next.Val {
			l1 = l1.Next
		} else {
			temp := *l1
			l1.Next = l2.Next
			l2.Next = l2.Next.Next
			l1.Next.Next = temp.Next
		}
	}
	if l2.Next != nil {
		l1.Next = l2.Next
	}
	return l1Prefix.Next
}
//leetcode submit region end(Prohibit modification and deletion)
